package priority;

import java.util.Arrays;

/**
 * 有序索引堆
 */
public class IndexMinPriorityQueue<T extends Comparable<T>> {
    private T[] items;
    private int[] qp;
    private int[] pq;
    private int N;

    public IndexMinPriorityQueue(int capacity) {
        items = (T[]) new Comparable[capacity + 1];
        pq = new int[capacity + 1];
        qp = new int[capacity + 1];
        N = 0;
        Arrays.fill(qp, -1);
    }

    private boolean max(int i, int j) {
        return items[pq[i]].compareTo(items[pq[j]]) > 0;
    }

    public void exchange(int i, int j) {
        // pq
        int temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
        //qp
        qp[pq[i]] = i;
        qp[pq[j]] = j;

    }

    public int delMin() {
        int minIndex = pq[1];
        exchange(1, N);
        items[pq[N]] = null;
        // 消除关联
        qp[pq[N]] = -1;
        pq[N] = -1;
        N--;
        sink(1);

        return minIndex;
    }

    private void sink(int k) {
        while (k * 2 <= N) {
            int min;
            if (k * 2 + 1 <= N) {
                // 有右
                if (max(2 * k, 2 * k + 1)) {
                    min = 2 * k + 1;
                } else {
                    min = 2 * k;
                }
            } else {
                min = 2 * k;
            }
            if (max(min, k)) {
                break;
            }
            exchange(min, k);
            k = k * 2;
        }
    }



    public void insert(int i, T t) {
        //如果索引i处已经存在了元素，则不让插入
        if (contains(i)) {
            throw new RuntimeException("该索引已经存在");
        }
        //个数+1
        N++;
        //把元素存放到items数组中
        items[i] = t;
        //使用pq存放i这个索引
        pq[N] = i;
        //在qp的i索引处存放N
        qp[i] = N;
        //上浮items[pq[N]],让pq堆有序
        swim(N);

    }

    private void swim(int k) {
        while (k > 1) {
            if (max(k / 2, k)) {
                exchange(k / 2, k);
            }
            k = k / 2;
        }
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public boolean contains(int i) {
        return qp[i] != -1;
    }

    public void delete(int i) {
        // 获取关联索引
        int k = qp[i];
        // 吧要删除的放到最后面
        exchange(k, N);
        // 删除关联
        qp[pq[N]] = -1;
        pq[N] = -1;
        items[i] = null;
        N--;
        // 保证元素有序
        // 从k处下沉
        sink(k);
        // 从k处上浮
        swim(k);

    }

    public void changeItem(int i, T t) {
        items[i] = t;
        int k = qp[i];
        // 保证元素有序
        // 从k处下沉
        sink(k);
        // 从k处上浮
        swim(k);
    }

    public int minIndex() {
        return pq[1];
    }

    public T get(int i) {
        return items[i];
    }


    public static void main(String[] args) {
        String[] arr = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
        IndexMinPriorityQueue<String> indexMinPQ = new IndexMinPriorityQueue<>(20);
        //插入
        for (int i = 0; i < arr.length; i++) {
            indexMinPQ.insert(i, arr[i]);
        }
        System.out.println(indexMinPQ.size());
        //获取最小值的索引
        System.out.println(indexMinPQ.minIndex());
        //测试修改
        indexMinPQ.changeItem(0, "Z");

        while (!indexMinPQ.isEmpty()) {

            System.out.print(indexMinPQ.delMin());
        }
    }


}
